#ifndef DICTIONARYCORE_H_INCLUDED
#define DICTIONARYCORE_H_INCLUDED

#include "MemoryManager.h"
#include "Console.h"

namespace CEngine {

template<typename E, typename K>
const typename Dictionary<E,K>::Node* const Dictionary<E,K>::nil = Dictionary<E,K>::createNil();

template<class E, class K>
Dictionary<E,K>::Node::Node(void)
    :   parent((Node*)nil),
        left((Node*)nil),
        right((Node*)nil),
        element(),
        key(),
        level(0)
{}

template<class E, class K>
Dictionary<E,K>::Node::Node(const Dictionary<E,K>::Node* l, const Dictionary<E,K>::Node* r)
    :   parent((Node*)nil),
        left((Node*)l),
        right((Node*)r),
        element(),
        key(),
        level(0)
{}

template<class E, class K>
Dictionary<E,K>::Dictionary(void)
    :   array(),
        root((Node*)nil),
        keyOffset(0),
        relativeKey(false)
{}

template<class E, class K>
Dictionary<E,K>::Dictionary(const E& element, const K& key)
    :   array(),
        root((Node*)nil),
        keyOffset(0),
        relativeKey(true)
{
    ///key must be from the first element of the vector!
    ASSERT(&key < (K*)(&element + 1));

    keyOffset = (U64)&key - (U64)&element;

    Node node;
    node.element = element;
    node.key = key;
    node.level = 1;
    array.pushBack(node);
    root = &array.back();
}

template<class E, class K>
Dictionary<E,K>::Dictionary(const Dictionary& dict)
    :   array(dict.array),
        root(dict.root),
        keyOffset(dict.keyOffset),
        relativeKey(dict.relativeKey)
{
    I64 offset = (U64)array.getRawArray() - (U64)dict.array.getRawArray();

    if(root != nil) {
        root += offset;
    }

    Iterator<E,K> it = array.begin();
    while(it != array.end()) {
        (*it).parent += offset;
        (*it).left += offset;
        (*it).right += offset;
        ++it;
    }
}

template<class E, class K>
Dictionary<E,K>::Dictionary(const Vector<E>& vect, const K& key)
    :   array(),
        root((Node*)nil),
        keyOffset(0),
        relativeKey(true)
{
    ///key must be from the first element of the vector!
    ASSERT(&key < (K*)((U64)vect.getRawArray() + sizeof(E)));

    keyOffset = (U64)&key - (U64)vect.getRawArray();

    Iterator<E,K> it = vect.begin();
    while(it != vect.end()) {
        insert(*it);
        ++it;
    }
}

template<class E, class K>
template<class T>
Dictionary<E,K>::Dictionary(const Iterator<T>& first, const Iterator<T>& last, const K& key)
    :   array(),
        root((Node*)nil),
        keyOffset(0),
        relativeKey(true)
{
    ///key must be from the first element of the vector!
    ASSERT(&key < (K*)((U64)&(*first) + sizeof(T)));

    keyOffset = (U64)&key - (U64)(&(*first));

    Iterator<T> it = first;
    while(it != last) {
        insert(*it);
        ++it;
    }
}

template<class E, class K>
Dictionary<E,K>&
Dictionary<E,K>::operator=(const Dictionary<E,K>& dict) {
    if(&dict == this) {
        return *this;
    }

    array = dict.array;
    root = dict.root;
    keyOffset = dict.keyOffset;
    relativeKey = dict.relativeKey;

    I64 offset = (U64)array.getRawArray() - (U64)dict.array.getRawArray();

    if(root != nil) {
        root += offset;
    }

    Iterator<E,K> it = array.begin();
    while(it != array.end()) {
        (*it).parent += offset;
        (*it).left += offset;
        (*it).right += offset;
        ++it;
    }

    return *this;
}

template<class E, class K>
Dictionary<E,K>&
Dictionary<E,K>::operator=(const Vector<E>& vect) {
    ASSERT(relativeKey == true);

    array.clear();
    array.reserve(vect.getSize());
    root = nil;

    Iterator<E> it = vect.begin();
    while(it != vect.end()) {
        insert(*it);
        ++it;
    }

    return *this;
}

template<class E, class K>
Dictionary<E,K>::~Dictionary(void) {}

template<class E, class K>
typename Dictionary<E,K>::DictionaryIterator Dictionary<E,K>::begin(void) const {
    Node* temp = root;
    while(temp->left != nil) {
        temp = temp->left;
    }

    DictionaryIterator it = {0};
    it.basePointer = const_cast<Dictionary<E,K>*>(this);
    it.currentPointer = const_cast<Dictionary<E,K>::Node*>(temp);

    return it;
}

template<class E, class K>
typename Dictionary<E,K>::DictionaryIterator Dictionary<E,K>::rBegin(void) const {
    Node* temp = root;
    while(temp->right != nil) {
        temp = temp->right;
    }

    DictionaryIterator it = {0};
    it.basePointer = const_cast<Dictionary<E,K>*>(this);
    it.currentPointer = const_cast<Dictionary<E,K>::Node*>(temp);

    return it;
}

template<class E, class K>
typename Dictionary<E,K>::DictionaryIterator Dictionary<E,K>::end(void) const {
    DictionaryIterator it = {0};
    it.basePointer = const_cast<Dictionary<E,K>*>(this);
    it.currentPointer = const_cast<Dictionary<E,K>::Node*>(nil);

    return it;
}

template<class E, class K>
typename Dictionary<E,K>::DictionaryIterator Dictionary<E,K>::insert(const E& element) {
    if(!relativeKey) {
        defaultLog.log(Logging::CONTAINERS, LOG_ERROR, "relativeKey must be set to use relative key insert!\n");
        return end();
    }
    K key = *(K*)((void*)&element + keyOffset);

    if(root == nil) {
        Node temp;
        temp.element = element;
        temp.key = key;
        temp.level = 1;
        array.pushBack(temp);
        root = &array.back();
        return createIterator(root);
    }
    else {
        Node* current = root;
        Node* newNode = root;
        Node* stack[256];
        U8 top = 0;
        bool greaterThan = false;

        while(true) {
            stack[top++] = current;
            greaterThan = (key > current->key);

            if(key == current->key) {
                return createIterator(current);
            }

            if(greaterThan) {
                if(current->right == nil) {
                    Node temp;
                    temp.element = element;
                    temp.key = key;
                    temp.level = 1;
                    temp.parent = current;

                    array.pushBack(temp);
                    newNode = current->right = &array.back();

                    break;
                }
                current = current->right;
            }
            else {
                if(current->left == nil) {
                    Node temp;
                    temp.element = element;
                    temp.key = key;
                    temp.level = 1;
                    temp.parent = current;

                    array.pushBack(temp);
                    newNode = current->left = &array.back();

                    break;
                }
                current = current->left;
            }
        }

        do {
            --top;
            if(top != 0) {
                greaterThan = stack[top - 1]->right == stack[top];
            }

            stack[top] = skew(stack[top]);
            stack[top] = split(stack[top]);

            if(top != 0) {
                if(greaterThan) {
                    stack[top - 1]->right = stack[top];
                }
                else {
                    stack[top - 1]->left = stack[top];
                }
                stack[top]->parent = stack[top - 1];
            }
            else {
                root = stack[top];
                root->parent = (Node*)nil;
            }
        } while (top != 0);
        return createIterator(newNode);
    }
}

template<class E, class K>
typename Dictionary<E,K>::DictionaryIterator Dictionary<E,K>::insert(const E& element, const K& key) {
    if(relativeKey) {
        defaultLog.log(Logging::CONTAINERS, LOG_WARNING, "Relative key insert should be used when relativeKey is set!");
    }

    if(root == nil) {
        Node temp;
        temp.element = element;
        temp.key = key;
        temp.level = 1;
        array.pushBack(temp);
        root = &array.back();
        return createIterator(root);
    }
    else {
        Node* current = root;
        Node* newNode = root;
        Node* stack[256];
        U8 top = 0;
        bool greaterThan = false;

        while(true) {
            stack[top++] = current;
            greaterThan = (key > current->key);

            if(key == current->key) {
                return createIterator(current);
            }

            if(greaterThan) {
                if(current->right == nil) {
                    Node temp;
                    temp.element = element;
                    temp.key = key;
                    temp.level = 1;
                    temp.parent = current;

                    array.pushBack(temp);
                    newNode = current->right = &array.back();

                    break;
                }
                current = current->right;
            }
            else {
                if(current->left == nil) {
                    Node temp;
                    temp.element = element;
                    temp.key = key;
                    temp.level = 1;
                    temp.parent = current;

                    array.pushBack(temp);
                    newNode = current->left = &array.back();

                    break;
                }
                current = current->left;
            }
        }

        do {
            --top;

            if(top != 0) {
                greaterThan = stack[top - 1]->right == stack[top];
            }

            stack[top] = skew(stack[top]);
            stack[top] = split(stack[top]);

            if(top != 0) {
                if(greaterThan) {
                    stack[top - 1]->right = stack[top];
                }
                else {
                    stack[top - 1]->left = stack[top];
                }
                stack[top]->parent = stack[top - 1];
            }
            else {
                root = stack[top];
                root->parent = (Node*)nil;
            }
        } while (top != 0);
        return createIterator(newNode);
    }
}

template<class E, class K>
void Dictionary<E,K>::erase(const K& key) {
    if(root == nil) {
        return;
    }

    Node* current = root;
    Node* stack[256];
    U8 top = 0;
    bool greaterThan = false;

    while(true) {
        stack[top++] = current;

        if(current == nil) {
            return;
        }
        if(current->key == key) {
            break;
        }

        greaterThan = (key > current->key);
        if(greaterThan) {
            current = current->right;
        }
        else {
            current = current->left;
        }
    }

    if(current->left == nil || current->right == nil) {
        bool tempRight = current->right != nil;

        if(--top != 0) {
            if(greaterThan) {
                if(tempRight) {
                    stack[top - 1]->right = current->right;
                }
                else {
                    stack[top - 1]->right = current->left;
                }
            }
            else {
                if(tempRight) {
                    stack[top - 1]->left = current->right;
                }
                else {
                    stack[top - 1]->left = current->left;
                }
            }
            current->parent = stack[top - 1];
        }
        else {
            root = current->right;
            root->parent = current;
        }
    }
    else {
        Node* heir = current->right;
        Node* previous = current;

        while(heir->left != nil) {
            stack[top++] = previous = heir;
            heir = heir->left;
        }

        current->element = heir->element;
        current->key = heir->key;
        if(previous == current) {
            heir->right->parent = previous->left;
            previous->left = heir->right;
        }
        else {
            heir->right->parent = previous->right;
            previous->right = heir->right;
        }
    }

    do {
        --top;

        if(top != 0) {
            greaterThan = stack[top - 1]->right == stack[top];
        }

        if (stack[top]->left->level < (stack[top]->level - 1)
         || stack[top]->right->level < (stack[top]->level - 1)) {
            if (stack[top]->right->level > --stack[top]->level) {
                stack[top]->right->level = stack[top]->level;
            }

            stack[top] = skew(stack[top]);
            stack[top]->right = skew(stack[top]->right);
            stack[top]->right->right = skew(stack[top]->right->right);
            stack[top] = split(stack[top]);
            stack[top]->right = split(stack[top]->right);
        }

        if(top != 0) {
            if(greaterThan) {
                stack[top - 1]->right = stack[top];
            }
            else {
                stack[top - 1]->left = stack[top];
            }
            stack[top]->parent = stack[top - 1];
        }
        else {
            root = stack[top];
            root->parent = (Node*)nil;
        }
    } while (top != 0);

    Iterator<Node> it = array.begin();
    for (; (*it).key != key; ++it) {}

    Node* cutOff = array.getRawArray() + it.getPosition();
    array.erase(it);

    it = array.begin();
    while(it != array.end()) {
        if((*it).left != nil && (*it).left >= cutOff) {
            --(*it).left;
        }
        if((*it).right != nil && (*it).right >= cutOff) {
            --(*it).right;
        }
        ++it;
    }
}

template<class E, class K>
void Dictionary<E,K>::clear(void) {
    array.clear();
    root = (Node*)nil;
}

template<class E, class K>
bool Dictionary<E,K>::isEmpty(void) const {
    if(root == nil) {
        return true;
    }
    else {
        return false;
    }
}

template<class E, class K>
U64 Dictionary<E,K>::getSize(void) const {
    return array.getSize();
}

template<class E, class K>
void Dictionary<E,K>::printTree(void) const {
    U32 count = 0;
    for (U32 i = 0; i < getSize(); ++i) {
        Console::print("%u. Key: %llu\tLevel: %u\n", ++count, array.getRawArray()[i].key, array.getRawArray()[i].level);

        if(array.getRawArray()[i].left == nil)
            Console::print("Left: nil\t\t");
        else
            Console::print("Left: %llu\t\t", array.getRawArray()[i].left->key);

        if(array.getRawArray()[i].right == nil)
            Console::print("Right: nil\n");
        else
            Console::print("Right: %llu\n", array.getRawArray()[i].right->key);

        if(array.getRawArray()[i].parent == nil)
            Console::print("Parent: nil\n\n");
        else
            Console::print("Parent: %llu\n\n", array.getRawArray()[i].parent->key);
    }
    Console::print("\n\n");
}

template<class E, class K>
typename Dictionary<E,K>::Node* Dictionary<E,K>::skew(typename Dictionary<E,K>::Node* root) {
    if((root->left->level == root->level) && (root->level != 0)) {
        Node* temp = root;

        root = root->left;

        temp->left = root->right;
        if(temp->left != nil) {
            temp->left->parent = temp;
        }

        root->right = temp;
        root->parent = temp->parent;
        temp->parent = root;
    }
    return root;
}

template<class E, class K>
typename Dictionary<E,K>::Node* Dictionary<E,K>::split(typename Dictionary<E,K>::Node* root) {
    if(root->level != 0 && root->right->right->level == root->level) {
        Node* temp = root;
        Node* parent = root->parent;

        root = root->right;

        temp->right = root->left;
        if(temp->right != nil) {
            temp->right->parent = temp;
        }

        root->left = temp;
        root->parent = temp->parent;
        temp->parent = root;
        ++root->level;
    }
    return root;
}

template<class E, class K>
typename Dictionary<E,K>::Node* Dictionary<E,K>::search(K key) {
    Node* node = root;
    bool greaterThan = false;

    while(true) {
        if(node->key == key || node == nil) {
            break;
        }

        greaterThan = (key > node->key);
        if(greaterThan) {
            node = node->right;
        }
        else {
            node = node->left;
        }
    }
    return node;
}

template<class E, class K>
typename Dictionary<E,K>::DictionaryIterator Dictionary<E,K>::createIterator(const Dictionary<E,K>::Node* node) const {
    DictionaryIterator it = {0};
    it.basePointer = const_cast<Dictionary<E,K>*>(this);
    it.currentPointer = const_cast<Dictionary<E,K>::Node*>(node);

    return it;
}

template<class E, class K>
typename Dictionary<E,K>::Node* Dictionary<E,K>::createNil(void) {
    Node* temp = new Node;
    temp->parent = temp;
    temp->right = temp;
    temp->left = temp;
    return temp;
}

}

#endif // DICTIONARYCORE_H_INCLUDED
